package com.wu.hassubtree;

/**
 * 树的子结构
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        //判断两个子树节点的值是否相等
        if (root1.val == root2.val) {//相等
            if (judgeSub(root1, root2)) {
                return true;//接着判断
            }
        }
        //如果不等，则遍历大树的左右子树
        return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

    private boolean judgeSub(TreeNode root, TreeNode sub) {
        //如果子结构为null则遍历完毕,包含
        if (sub == null) {
            return true;
        }
        //如果父结构为null则遍历完毕,不包含
        if (root == null) {
            return false;
        }
        //判断是否相等
        if (root.val == sub.val) {
            //判断左右子树
            return judgeSub(root.left, sub.left) && judgeSub(root.right, sub.right);
        }
        return false;
    }
}